Databases are ubiquitous. As information is accumulated, a database inevitably emerges, both to maintain and to access the information. The vast stores of information upon which many organizations depend have, in many instances, grown unwieldy. Tools for accessing the data continue to be developed at a rapid rate.
With such demands driving the industry, the optimization of query operations is an ongoing feature of database software development. Take, for example, the plethora of types of indexing methods. Indices provide a mechanism for finding a row (also known as a tuple) of a table (also known as a relation) from possibly millions of rows. Hash indices and B-trees are two common indexing types. More recently, with the availability of spatial objects in databases, R-trees and R*-trees, are used for efficient access to the objects.
Another index, known as a join index, is a type of xe2x80x9cprecomputedxe2x80x9d join operation between two or more tables of data. A join index is a data structure that tries to store enough information to accelerate join operations between tables of data. In practice, a join index is a distinct table including record identifiers from two or more existing tables. To compute a join, the record identifiers in the join index are sorted for efficient fetching of tuples from the tables.
Increasingly, spatial data types form part of the database data. Spatial join indices have been proposed to aid efficient spatial join formation. For example, these spatial join indices may employ a grid file, which is a point data index structure, to index the spatial join attributes. Unfortunately, the grid file limits the spatial join index to only point data rather than polygon data. Furthermore, the original spatial join index may only be used in a uni-processor environment. Thus, the known spatial join indices are unsuitable for applications such as data warehousing where parallelism is crucial for optimal performance.
In accordance with the embodiments described herein, a method is disclosed in which a portion of a join index is received into a memory. The join index comprises first record identifiers from a first table and second record identifiers from a second table. In memory, the join index is sorted according to first record identifiers from the first table. The portion of the join index is resorted according to second record identifiers from the second table. Join operations are performed between first and second spatial join attributes using the resorted portion of the join index.
Other features and embodiments will become apparent from the following description, from the drawings, and from the claims.